package com.pandy.leetcode;


/**
 * @description: 二叉树递归套路练习
 * 判断是否是平衡二叉树
 *
 * https://leetcode.cn/problems/ping-heng-er-cha-shu-lcof/description/
 * @author: panhong
 * @date: 2025/3/31
 */
public class Code004_BinaryTree_Balance {

    public static boolean isBalance(BinaryTreeNode head) {
        return process(head).isBalance;
    }

    static class Info {
        private boolean isBalance;
        private int height;

        public Info(boolean isBalance, int height) {
            this.isBalance = isBalance;
            this.height = height;
        }
    }

    public static Info process(BinaryTreeNode x) {
        if(x == null) {
            return new Info(true, 0);
        }

        Info leftInfo = process(x.left);
        Info rightInfo = process(x.right);

        boolean isBalance = false;

        // 左右子树都平衡，才是平衡二叉树
        if(leftInfo.isBalance && rightInfo.isBalance) {
            isBalance = true;
        }
        int height = Math.max(leftInfo.height, rightInfo.height) + 1;

        // 平衡二叉树：左右高度差不能超过1
        if(Math.abs(leftInfo.height - rightInfo.height) > 1) {
            isBalance = false;
        }

        return new Info(isBalance,height);
    }

    public static void main(String[] args) {
        BinaryTreeNode n1 = new BinaryTreeNode(1);
        BinaryTreeNode n2 = new BinaryTreeNode(2);
        BinaryTreeNode n3 = new BinaryTreeNode(3);
        BinaryTreeNode n4 = new BinaryTreeNode(4);
        BinaryTreeNode n5 = new BinaryTreeNode(5);


        BinaryTreeNode n6 = new BinaryTreeNode(6);
        BinaryTreeNode n7 = new BinaryTreeNode(7);
        BinaryTreeNode n8 = new BinaryTreeNode(8);

        n1.left = n2;
        n1.right = n3;
        n2.left = n4;
        n4.left = n5;

        n2.left = n6;

        System.out.println(isBalance(n1));
    }
}
